#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 110;

bool f[N][N], v1[N], v2[N], hav[N], ban[N], tans[N];
int mat[N], n, m, ans, tim;
int vis[N];
vec G[N];

bool dfs(int x) {
	v1[x] = true; if(ban[x]) return false;
	for(auto y : G[x])
		if(!ban[y] && vis[y] != tim) {
			vis[y] = tim; v2[y] = true;
			if(!mat[y] || dfs(mat[y])) return mat[y] = x, hav[x] = true, true;
		}
	return false;
}

int calc(int ans = ::n) { rep(i, 1, n) { ++tim; if(dfs(i)) ans--; } return ans; }

bool check(int x) {
	rep(i, 1, n) mat[i] = 0, ban[i] = false; 
	int cnt = n; rep(i, 1, n) if(f[i][x] || f[x][i] || x == i) ban[i] = true, cnt--;
	return calc(cnt) == ans - 1;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; rep(i, 1, m) { int u = in, v = in; f[u][v] = true; }
	rep(k, 1, n) rep(i, 1, n) if(f[i][k] && i ^ k) rep(j, 1, n) if(f[k][j] && j ^ k && i ^ j) f[i][j] = true;
	rep(i, 1, n) rep(j, 1, n) if(i ^ j && f[i][j]) G[i].eb(j);
	printf("%d\n", ans = calc());
	rep(i, 1, n) v1[i] = v2[i] = 0;
	rep(i, 1, n) if(!hav[i]) ++tim, dfs(i);
	rep(i, 1, n) printf("%d", tans[i] = (v1[i] && !v2[i])); // duliji
	puts(""); rep(i, 1, n) printf("%d", check(i)); puts("");
	return 0;
}
